package HashTablePackage;

import com.sun.source.tree.WhileLoopTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class threeSum_ {
  public static void main(String[] args) {
    int[] nums = new int[]{1,-1,-1,0};
    System.out.println(threeSum2(nums));
    System.out.println(threeSum(nums));
  }
  public static List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      /*对数组nums进行排序*/
      Arrays.sort(nums);
      if (nums.length <3 || nums[0] > 0 || nums[nums.length - 1] < 0){
        return null;
      }
      for (int i = 0 ; i < nums.length ; i ++){
        /*去重*/
        if (i > 0 && nums[i] == nums[i - 1]){
          continue;
        }
        int left = i + 1;
        int right = nums.length - 1;
        while(left < right){ // 边界判断, 当left == right时, i left right 一共就二个值, 不能得到正确结果
          if (nums[i] + nums[left] + nums[right] > 0){
            right--;
          }
          else if(nums[i] + nums[left] + nums[right] < 0){
            left++;
          }
          else if(nums[i] + nums[left] + nums[right] == 0) {
            List<Integer> list = new ArrayList<>();
            list.add(nums[i]);
            list.add(nums[left]);
            list.add(nums[right]);
            result.add(list);
            while(left < right && nums[left] == nums[left + 1]) {
              left++;
            } while (left < right && nums[right] == nums[right - 1]) {
              right--;
            }
            right--;
            left++;
          }
        }
      }
      return result;
  }

  public static List<List<Integer>> threeSum2(int[] nums) {
      List<List<Integer>> result = new ArrayList<>();
      Arrays.sort(nums);
      // 找出a + b + c = 0
      // a = nums[i], b = nums[left], c = nums[right]
      for (int i = 0; i < nums.length; i++) {
        // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
        if (nums[i] > 0) {
          return result;
        }

        if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
          continue;
        }

        int left = i + 1;
        int right = nums.length - 1;
        while (right > left) {
          if (nums[i] + nums[left] + nums[right] > 0) {
            right--;
          } else if (nums[i] + nums[left] + nums[right] < 0) {
            left++;
          } else {
            result.add(Arrays.asList(nums[i], nums[left], nums[right]));
            // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
            while (right > left && nums[right] == nums[right - 1]) right--;
            while (right > left && nums[left] == nums[left + 1]) left++;

            right--;
            left++;
          }
        }
      }
      return result;
    }
  public List<List<Integer>> threeSum3(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    if (nums[0] > 0){
      return result;
    }
    if (nums[nums.length - 1] < 0){
      return result;
    }
    int pointer = 0 ;
    int left = 1 ;
    int right = nums.length - 1;
    for (int i = 0 ; i < nums.length ; i++){
      if (i > 0 && nums[i] == nums[i - 1]){
        continue;
      }
      left = i + 1;
      right = nums.length - 1;
      while(left < right){
        if ((nums[i]+ nums[left] + nums[right]) < 0){
          left++;
        }
        else if ((nums[i]+ nums[left] + nums[right]) > 0){
          right--;
        }
        else if ((nums[i]+ nums[left] + nums[right]) == 0){
          List<Integer> list = new ArrayList<>();
          list.add(nums[i]);
          list.add(nums[left]);
          list.add(nums[right]);
          result.add(list);
          while(nums[left] == nums[left--]) left++;
          while(nums[right] == nums[right++]) right--;
          right--;
          left++;
        }
      }
    }
    return result;
  }
}
